package bfs;

import java.util.*;

public class OpenTheWheelLock {

    public int openLock(String[] deadends, String target) {
        // 记录需要跳过的死亡密码
        Set<String> deadSet = new HashSet<>();
        for (String s : deadends) deadSet.add(s);
        if (deadSet.contains("0000")) return -1;

        // 记录已经穷举过的密码，防止走回头路
        Set<String> visited = new HashSet<>();
        Queue<String> q = new LinkedList<>();

        // 从七点开始启动广度优先搜索
        int step = 0;
        q.offer("0000");
        visited.add("0000");

        while (!q.isEmpty()) {
            int sz = q.size();
            // 将当前队列中的所有节点向周围扩散
            for (int i = 0; i < sz; i++) {
                String cur = q.poll();

                // 判断是否到达终点
                assert cur != null;
                if (cur.equals(target)) {
                    return step;
                }

                // 将每一个节点的合法相邻节点加入队列
                for (String neighbor : getNeighbor(cur)) {
                    q.offer(neighbor);
                }
            }
            // 在这里增加步数
            step++;
        }
        return step;
    }

    /**
     * 将 s 的每一位向上或向下拨动一次，8 种相邻密码
     * @param s
     * @return
     */
    private List<String> getNeighbor(String s) {
        List<String> neighbors = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            neighbors.add(plusOne(s, i));
            neighbors.add(minusOne(s, i));
        }

        return neighbors;
    }

    private String minusOne(String s, int i) {
        char[] str = s.toCharArray();
        if (str[i] == '0')
            str[i] = '9';
        else
            str[i] -= 1;
        return new String(str);
    }

    private String plusOne(String s, int i) {
        char[] str = s.toCharArray();
        if (str[i] == '9')
            str[i] = '0';
        else
            str[i] += 1;
        return new String(str);
    }
}
